package linkedListQueue

import (
	"errors"
	"fmt"
	"strings"
)

type LinkedList[E any] struct {
	head, tail *node[E]
	size       int
}

func MakeLinkedList[E any]() *LinkedList[E] {
	dummyNode := makeNode[E]()
	return &LinkedList[E]{
		head: dummyNode,
		tail: dummyNode,
	}
}

// GetSize 获取链表中的元素个数
func (l *LinkedList[E]) GetSize() int {
	return l.size
}

// IsEmpty 返回链表是否为空
func (l *LinkedList[E]) IsEmpty() bool {
	return l.size == 0
}

// AddLast 在链表末尾添加新的元素e
func (l *LinkedList[E]) AddLast(e E) error {
	l.tail.next = makeNode1(e)
	l.tail = l.tail.next
	l.size++
	return nil
}

// Get 获得链表的第index(0-based)个位置的元素
// 索引操作，在链表中不是一个常用的操作，练习用
func (l *LinkedList[E]) Get(index int) (E, error) {
	var zero E
	if index < 0 || index >= l.size {
		return zero, errors.New("get failed. Illegal index")
	}
	//获取当前索引的节点
	cur := l.head.next
	for i := 0; i < index; i++ {
		cur = cur.next
	}
	return cur.e, nil
}

// GetFirst 获得链表的第一个元素
func (l *LinkedList[E]) GetFirst() (E, error) {
	return l.Get(0)
}

// GetLast 获得链表的最后一个元素
func (l *LinkedList[E]) GetLast() (E, error) {
	return l.Get(l.size - 1)
}

// RemoveFirst 从链表中删除第一个元素，返回删除的元素
func (l *LinkedList[E]) RemoveFirst() (E, error) {
	var zero E
	if l.size == 0 {
		return zero, errors.New("cannot dequeue from an empty queue")
	}
	headNode := l.head.next
	l.head.next = headNode.next
	headNode.next = nil
	return headNode.e, nil
}

func (l *LinkedList[E]) String() string {
	sb := strings.Builder{}
	sb.WriteString("Queue: front ")

	for cur := l.head.next; cur != nil; cur = cur.next {
		sb.WriteString(fmt.Sprintf("%s->", cur))
	}
	sb.WriteString("NULL tail")
	return sb.String()
}
